#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
@ Author: CJK_Monomania
@ Data: 2021-12-21
"""

from typing import *
from pprint import pprint
import sys   # sys.maxsize---int的最大值

'''
@ 题目: Python
@ 参考链接: 
int最大值: sys.maxsize
float最大值: float('inf')
'''
# Definition for singly-linked list.--链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next



class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if head is None or head.next is None:
            return
        mid = self.FindMidNode(head)
        L1 = head
        # L2 = mid.next
        # mid.next = None  # 这一步不能少
        L2 = mid
        mid = None  # 这一步不能少
        L2 = self.ReverseList(L2)
        self.mergeList(L1, L2)
    

    def FindMidNode(self, head: ListNode) -> ListNode:
        low = head
        fast = head
        while (fast.next is not None) and (fast.next.next is not None):
            low = low.next
            fast = fast.next.next
        
        return low

    def ReverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while(cur != None):
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
        return pre
    
    def mergeList(self, l1: ListNode, l2: ListNode):
        while (l1 is not  None and l2 is not None):
            temp1 = l1.next
            temp2 = l2.next
            
            l1.next = l2
            l1 = temp1

            l2.next = l1
            l2 = temp2


def main():
    solu = Solution()
    print(solu.function())


if __name__ == '__main__':
    main()